package com.gxc.heap;

import java.util.*;

/**
 * 为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。
 * 牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。
 * 在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作。
 * 牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
 * class Job[
 * 	public int money;// 该工作的报酬
 * 	public int hard;// 该工作的难度
 * 	public Job(int money, int hard) {
 * 		this.money = money;
 * 		this.hard = hard;
 *        }
 * 给定一个Job类型的数组jobarr，表示所有的工作。给定一个int类型的数组arr，表示所有小伙伴的能力。
 * 返回int类型的数组，表示每一个小伙伴按照牛牛的标准选工作后所能获得的报酬。
 *
 * 解法：
 * 1.小伙伴的能力从小到大排序
 * 数组排序
 * 2.工作先按难度排序，再按报酬，同难度低报酬的工作删除，难度高，报酬却低的工作删除
 * map过滤同难度低报酬的工作，小根堆过滤难度高，报酬却低的工作
 */
public class AssigningJob {

    public static void main(String[] args) {
        int size = 1000;
        for (int i = 0; i < size; i++) {
            Job[] jobarr = randJob();
            int[] arr = rand();
            int[] assign = assign(jobarr, arr);
            int[] assign2 = assign2(jobarr, arr);
            if (!compare(assign, assign2)) {
                printJob(jobarr);
                printArr(arr);
                System.out.println("算法有问题");
                break;
            }
        }
        System.out.println("结束");

        Job[] testjobarr = testrandJob();
        int[] testarr = testrand();
        int[] assign = assign(testjobarr, testarr);
        int[] assign2 = assign2(testjobarr, testarr);
        if (!compare(assign, assign2)) {
            printJob(testjobarr);
            printArr(testarr);
            System.out.println("算法有问题");
        }
    }

    private static int[] testrand() {
        return new int[]{10, 10};
    }

    private static Job[] testrandJob() {
        Job[] jobs = new Job[8];
        jobs[0] = new Job(6, 1);
        jobs[1] = new Job(10, 3);
        jobs[2] = new Job(2, 3);
        jobs[3] = new Job(11, 4);
        jobs[4] = new Job(3, 4);
        jobs[5] = new Job(6, 5);
        jobs[6] = new Job(7, 9);
        jobs[7] = new Job(5, 9);
        return jobs;
    }

    /**
     * @param jobarr    Job类型的数组
     * @param arr       小伙伴的能力数组
     * @return
     */
    public static int[] assign(Job[] jobarr, int[] arr) {
        //map过滤同难度低报酬的工作
        Map<Integer, Job> jobMap = new HashMap<>();
        for (int i = 0; i < jobarr.length; i++) {
            Job cur = jobarr[i];
            Job exist = jobMap.get(cur.hard);
            if (exist == null) {
                jobMap.put(cur.hard, cur);
            } else {
                if (cur.money > exist.money) {
                    jobMap.put(cur.hard, cur);
                }
            }
        }
        //小根堆过滤难度高，报酬却低的工作
        //queue先排序已过滤后的工作
        PriorityQueue<Job> queue = new PriorityQueue<>(new JobComparator());
        Iterator<Map.Entry<Integer, Job>> iterator = jobMap.entrySet().iterator();
        while (iterator.hasNext()) {
            queue.add(iterator.next().getValue());
        }
        //queue2 丢弃难度高，报酬却低的工作
        int maxmoney = 0;
        PriorityQueue<Job> queue2 = new PriorityQueue<>(new JobComparator());
        while (!queue.isEmpty()) {
            Job cur = queue.poll();
            if (cur.money>maxmoney) {
                maxmoney = cur.money;
                queue2.add(cur);
            }
        }
        //小伙伴的能力从小到大排序
        Arrays.sort(arr);

        int[] result = new int[arr.length];
        Job curJob = null;
        for (int i = 0; i < arr.length; i++) {
            int ability = arr[i];
            if (curJob!=null) {
                result[i] = curJob.money;
            }
            while (!queue2.isEmpty()) {
                if (queue2.peek().hard<=ability) {
                    curJob = queue2.poll();
                    result[i] = curJob.money;
                } else {
                    break;
                }
            }
        }

        return result;
    }


    public static int[] assign2(Job[] jobarr, int[] arr) {
        //工作先按难度排序，再按报酬
        Arrays.sort(jobarr, new JobComparator2());

        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        int preMoney = 0;
        for (int i = 0; i < jobarr.length; i++) {
            Job job = jobarr[i];
            //同难度低报酬的工作删除，难度高报酬却低的工作删除
            if (!treeMap.containsKey(job.hard) && job.money>preMoney) {
                preMoney = job.money;
                treeMap.put(job.hard, job.money);
            }
        }

        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            //返回小于等于能力值的最大难度的工作
            Integer jobMax = treeMap.floorKey(arr[i]);
            result[i] = jobMax == null?0:treeMap.get(jobMax);
        }
        return result;
    }

    public static class Job {

        public int money;
        public int hard;

        public Job(int money, int hard) {
            this.money = money;
            this.hard = hard;
        }
    }

    public static class JobComparator implements Comparator<Job> {

        @Override
        public int compare(Job o1, Job o2) {
            return o1.hard - o2.hard;
        }
    }

    public static class JobComparator2 implements Comparator<Job> {

        @Override
        public int compare(Job o1, Job o2) {
            if (o1.hard == o2.hard) {
                return o2.money - o1.money;
            } else {
                return o1.hard - o2.hard;
            }
        }
    }

    private static int[] rand() {
        int size = (int) (Math.random() * 10) + 1;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (Math.random() * 10 + 1);
        }
        return arr;
    }

    /**
     *
     * @return
     */
    private static Job[] randJob() {
        int size = (int) (Math.random() * 10)+2;
        Job[] jobs = new Job[size];
        for (int i = 0; i < jobs.length; i++) {
            int money = (int) (Math.random() * 15 + 1);
            int hard = (int) (Math.random() * 10 + 1);
            Job job = new Job(money, hard);
            jobs[i] = job;
        }
        return jobs;
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }

    private static void printJob(Job[] jobarr) {
        for (int i = 0; i < jobarr.length; i++) {
            System.out.println("hard:" + jobarr[i].hard + ", money:" + jobarr[i].money);
        }
    }

    private static boolean compare(int[] assign, int[] assign2) {
        for (int i = 0; i < assign.length; i++) {
            if (assign[i]!=assign2[i]) return false;
        }
        return true;
    }

}
